/*********************************************************************
* File: QueuePriority.cpp
*
* \brief Implementation of a priority queue.
*********************************************************************/
#include "QueuePriority.h"
#include <malloc.h>
using namespace collections;

/**
* \brief The class constructor.
**/
QueuePriority :: QueuePriority( int heapSize )
{
   m_cSize = 0;
   m_cHeapSize = heapSize;
   m_heap = (struct tag_HEAP_NODE *)malloc(sizeof(struct tag_HEAP_NODE) * m_cHeapSize);
}

/**
* \brief The class destructor.
**/
QueuePriority :: ~QueuePriority( void )
{
   free(m_heap);
}

/**
* \brief Inserts a value into the priority queue.
**/
void QueuePriority :: Insert( int iValue, float fPriority )
{
   if ( m_cSize >= m_cHeapSize )
   {
      m_cHeapSize += 100;
      m_heap = (struct tag_HEAP_NODE *)realloc(m_heap, sizeof(struct tag_HEAP_NODE) * m_cHeapSize);
   }
   m_heap[m_cSize].Priority = fPriority;
   m_heap[m_cSize].Id = iValue;
   m_cSize++;
   Heap_SiftUp();
}

/**
* \brief Removes the smallest item from the priority queue.
**/
int QueuePriority :: Remove( void )
{
   int iReturn = m_heap[0].Id;
   m_cSize--;
   m_heap[0] = m_heap[m_cSize];
   Heap_SiftDown(0);
   return iReturn;
}

#define HEAP_LEFT_CHILD(x)    (2 * (x) + 1)
#define HEAP_RIGHT_CHILD(x)   (2 * (x) + 2)
#define HEAP_PARENT(x)        (((x) - 1) / 2)

/**
* 
**/
void QueuePriority::Heap_SiftDown(int iSubRoot)
{
   int parent = iSubRoot;
   int child = HEAP_LEFT_CHILD(parent);

   struct tag_HEAP_NODE Ref = m_heap[ parent ];

   while (child < m_cSize)
   {
      int rightchild = HEAP_RIGHT_CHILD(parent);
      if (rightchild < m_cSize)
      {
         if ( m_heap[rightchild].Priority < m_heap[child].Priority )
            child = rightchild;
      }
      if ( Ref.Priority <= m_heap[child].Priority )
         break;

      m_heap[parent] = m_heap[child];
      parent = child;
      child = HEAP_LEFT_CHILD(parent);
   }
   m_heap[parent] = Ref;
}
/**
* 
**/
void QueuePriority::Heap_SiftUp(void)
{
   int child = m_cSize - 1;
   while (child)
   {
      int parent = HEAP_PARENT(child);
      if ( m_heap[parent].Priority <= m_heap[child].Priority )
         break;

      struct tag_HEAP_NODE Tmp;
      Tmp = m_heap[child];
      m_heap[child] = m_heap[parent];
      m_heap[parent] = Tmp;

      child = parent;
   }
}
